package data_structures_and_algorithms.list_node.learn;

/**
 * @ClassName Code01_ReverseListNode
 * @Description: 反转链表：写在这里的都是模板代码
 * @Author: myl
 * @create_time: 2022/10/25 23:46
 */
public class Code01_ReverseListNode {

    static class ListNode{
        public int val;
        public ListNode next;

        public ListNode(int val){
            this.val = val;
        }
    }

    static class DoubleNode {
        public int val;
        public DoubleNode next;
        public DoubleNode last;

        public DoubleNode(int val){
            this.val = val;
        }
    }

    public static void printListNode(ListNode head){
        while (head != null){
            System.out.print(head.val + " ,");
            head = head.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
//        ListNode head = new ListNode(100);
//        ListNode cur = head;
//        for (int i = 0; i < 8; i++) {
//            cur.next = new ListNode(i);
//            cur = cur.next;
//        }
//        printListNode(head);
//        ListNode re = reverseListNode(head);
//        printListNode(re);

        DoubleNode head = new DoubleNode(100);
        DoubleNode cur = head;
        for (int i = 0; i < 9; i++) {
            DoubleNode node = new DoubleNode(i);
            cur.next = node;
            node.last = cur;
            cur = node;
        }
        DoubleNode reverseHead = reverseDoubleListNode(head);
        System.out.println("12");


    }


    public static ListNode reverseListNode(ListNode head){
        ListNode pre = null, cur = head;
        while (cur != null){
            // 记录下来当前节点的下一个节点
            ListNode next = cur.next;

            // 当前节点指向前一个节点
            cur.next = pre;
            pre = cur;

            // 移动cur指向到下一个节点，继续遍历
            cur = next;
        }

        return pre;
    }


    // 区别于循环链表
    public static DoubleNode reverseDoubleListNode(DoubleNode head) {
        // 创建pre节点，cur节点
        DoubleNode pre = null, cur = head, next = null;
        while (cur != null){
            // 记录下下一个节点
            next = cur.next;

            // 处理节点的前后指向关系
            cur.next = pre;
            if (pre != null){
                pre.last = cur;
            }
            cur.last = null;// 切断原本得last指向

            // 移动pre cur
            pre = cur;
            cur = next;
        }

        return pre;
    }


}
